package com.yincb.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 6, 1, 2, 7, 9, 3, 4, 5, 10, 8
 */
public class QuiklySort {


    public static void main(String[] args) {

        int[] data = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};

        int left = 0;
        int right = data.length - 1;

        qSort(data, left, right);

        System.out.println(Arrays.toString(data));
    }

    private static void qSort(int[] data, int left, int right) {

        int p1 = left;
        int p2 = right;
        int base = data[left];
        // 基准数取第一个
        while (p1 < p2) {

            while (p1 < p2 && data[p2] >= base) {
                p2--;
            }

            if (p1 < p2) {
                int tem = data[p1];
                data[p1] = data[p2];
                data[p2] = tem;
                p1++;
            }

            while (p1 < p2 && data[p1] <= base) {
                p1++;
            }

            if (p1 < p2) {
                int tem = data[p1];
                data[p1] = data[p2];
                data[p2] = tem;
                p2--;
            }

            if (left < p1) {
                qSort(data, left, p1 - 1);
            }

            if (p2 < right) {
                qSort(data, p1 + 1, right);
            }
        }


    }


}
